基于网络表征学习特征表达的机器学习框架
网络表征学习(network embedding)的目标是为网络中的每个节点学习一个特征表达。目前学术界已经有非常多的网络表征学习算法。文献[1]对此进行了综述。Deepwalk[4]和Node2vec[7]这两个算法主要用于网络局部信息的表达，如何在游走中选择邻居以及预设窗口大小是这两个算法的关键，直接影响特征表达的物理含义。这两个算法适用于描述用户的ego-network，比如计算好友间的社交相似性或者好友影响力，适用于好友推荐、用户的ego-network的社团划分、微信游戏的好友邀请策略、微信朋友圈广告推荐等业务。LINE[6]和SDNE[2]算法也是网络局部信息的表达，他们同时考虑节点之间的一阶关系和二阶关系，其使用场景与Deepwalk或者Node2vec相同。HOPE[3]算法的目标是为节点表达更为全局化的网络信息，适用于描述微信网络的全局特征。HNE-DA[5]算法是基于深度学习模型(deep model)方法对异构信息网络进行表达，Metapath2vec[9]是基于node2vec改进的异构信息网络的网络表征学习算法，这两种算法都适用于微信的异构信息网络；Struc2vec[8]的算法目标是为了表达节点的网络位置（节点中心性），该算法适用于关键节点挖掘、信息传播研究等场景。基于这些算法，我们根据微信的数据特性以及业务需求进行了算法适配和调参，实现了多种网络表征学习算法，建立了基于网络表征学习特征表达的机器学习应用框架。见图1。
图1 基于网络表征学习特征的机器学习应用框架
模块1：基础数据层。主要是输入网络数据，比如说好友关系数据。对于一些兴趣行为数据，也可以转换成为网络数据作为输入。
模块2：网络表征学习算法层。目前该层提供了矩阵分解、Line、Node2vec、Deepwalk、metapath2vec这几种算法，工程师可以根据自己的网络特征以及业务场景进行选择。
模块3：模型层。在网络表征学习算法层，实现的算法都是无监督算法。应用到不同的机器学习任务上，需要做特征交叉和特征选择。在模型层，系统封装了FM、xgboost、deep&wide model、HNN(Holistic Neural Network)、FNN以及LR算法。以HNN为例，网络表征学习产出的特征的应用架构如图2所示，模型框架融合了网络表征学习特征以及常用的人工设计的特征，进行业务建模。
在模型层使用同一个算法的前提下，相对原先以人工设计特征为主的特征表达方法，网络表征学习的产出特征使得多个业务的相关性能得到较好的提升。在社交lookalike广告项目中，用户点击率提升约15%；在微信表情推荐项目中，用户下载量提升6%以上；在游戏好友邀请下载的项目中，下载量提升5%。另外，对于社交关系网络的特征表达，可以复用到不同的社交推荐场景中，提高了工作效率。
图2 网络表征学习+HNN
大规模网络表征学习实现框架
在有限的机器资源下，如何实现微信关系链十亿级节点、千亿级关系条数的超大规模网络表征学习是我们要重点攻克的一个难题。我们自行研发了一套分布式计算系统架构——mmps4ml。该架构基于C语言开发，结合列式存储、Allreduce通讯模式等降低网络流量，并且实现变种 Skip-gram 模型，平衡参数间的更新频率，保证算法效果及收敛速度，使得速度得到大幅提升。Mmps4ml计算架构具体很好的复用性，可复用于计算密集的分布式机器学习任务。
随机游走的分布式实现
给定一个图G 和一个起始节点S，标记起始节点位置为当前位置，随机选择当前位置节点的一个邻居并将当前位置移动至被选择的邻居位置，重复以上步骤n次，最终会得到从初始节点到结束节点的一条长度为n的“点序列”，此条“点序列”称为在图G 上的一次随机游走(random walk)。由定义可以看出，随机游走算法关键分为2步：选择起始节点和选择下一跳节点。
在mmps4ml系统中，大规模随机游走算法是基于Spark + Parameter-Server实现的。Spark 是时下最流行的基于MapReduce模型的大数据处理框架，使用其提供的分布式内存抽象弹性分布式数据集(Resilient Distributed Datasets, RDD)及其衍生物Dataset可以非常容易地实现批量数据处理的算法。但是对于需要精确查找与迭代更新的算法，使用Spark不仅实现困难，往往性能也不理想。有鉴于此，李沐等人[10, 11]提出基于参数-服务器(Parameter-Server)形式的机器学习框架，解决当下基于MapReduce模型的大数据处理框架遇到的困难。如果直接使用原生Spark API 实现随机游走，一个直观做法是，首先依据待嵌入的图生成邻接表(NeighborsRDD)，随后使用图中所有节点作为当前节点(LocationsRDD)，算法运行每一步使用LocationsRDD连接(join) NeighborsRDD得到下一步的候选集(NextLocationsRDD)，再由NextLocationsRDD生成新的LocationsRDD，算法每一步将当前Locations保存至Hadoop分布式文件系统(HDFS)中，最后汇总形成随机游走序列。这种方法的劣势也很明显，如果需要做加权随机游走（比如Node2vec算法设置了参数p和q），每一步需要连接两次邻接表，产生两次洗牌(shuffle)过程，不仅在计算集群中产生巨大的中间结果，而且网络通信消耗巨大。因此，本文使用Spark对原始图做初步处理，形成邻接表推送至PS存储，随后依托PS批量查询操作完成随机过程。当网络节点数为1亿，网络平均度数为50时，使用Spark与PS进行随机游走的通讯量对比如表1所示。
表1 PS+Spark实现与Spark实现通讯量对比
由表1易见，相比Spark RDD连接，使用PS方式可以减少1/3的网络交互，加上完全省去了Shuffle带来的硬盘操作，PS上的随机游走不仅算法逻辑直观简单，而且时间效率上也远胜完全依赖Spark的实现。
Word2vec的大规模实现
目前业界公开的word2vec分布式实现主要是数据并行或者数据并行+PS(Parameter-Server)架构，这两者都存在单机内存消耗过大或者网络通讯总量过大的问题。Mmps4ml较好地解决了这两个问题。
在mmps4ml的框架下（见图3），Spark集群可以视为“计算节点”，PS-Server 可以视为“存储节点”。算法执行过程可以大致分成 2 步：首先，Spark负责由语料库（对应由微信关系链生成的随机游走序列）生成词汇表（对应微信用户表），使用文献[9]中的方法对所有词向量进行初始化并推送至PS-Server；随后，通过Spark将语料库切分成一个个minibatch训练集，并发多个minibatch的同时向PS-Server侧发起一轮训练请求，PS-Server侧多线程执行训练请求并更新局部词向量。
图3 mmps4ml计算框架图
在这个框架下，我们主要从降低网络通讯量、优化CPU和Cache利用率、调整算法以加速收敛这三个角度进行计算优化。
1.列式存储与Allreduce通讯模式，使得网络流量大幅度降低，向量存储方式使用列式存储替代行式存储，同时配合使用Hogwild MBGD训练方式、Allreduce广播模型和变种skip-gram模型，在不影响算法收敛速度和效果的情况下，使得分布式一轮计算过程中整体通讯量下降到原来的10%左右，使得计算时间缩短至1/10。
2.使用内积离散化技术将网络中传输的向量点乘结果从4个字节压缩为1个字节。实验结果表明，在不影响算法收敛速度和效果的前提下，可以将计算过程中的整体通讯量减少到原始算法的1/4左右，从而大幅缩短算法运行所需时间。
3.状态记录：增加parameter server对session的支持，减少训练过程中重复数据的传输，有效减少算法运行过程中的通讯消耗。
4.使用范围负采样技术提高计算过程中的CPU Cache利用率，在不显著增加计算时间的情况下（2倍原始耗时以内），将负采样次数提升了10倍以上，从而大幅缩短算法收敛时间。
所有的优化方法见表2。
表2 mmps4ml实现word2vec优化点汇总
后续研究
随着微信业务的不断发展，网络表征学习算法也面临更大的挑战，未来我们的工作会聚焦在以下两个方面：建立时序网络的表征学习算法，表达用户的社交特征的变迁、兴趣特征随时间的衰退或增强；建立端对端的网络表征学习算法机制，将网络表征学习的特征表达能力直接对接业务，进行更加有效的表达。
（其他作者：贺鹏、于东海）
参考文献
[1] Cui P, Wang X, Pei J, et al. A Survey on Network Embedding[OL]. (2017-11-23).arXiv preprint arXiv:1711.08752.
[2] Wang D, Cui P, Zhu W. Structural Deep Network Embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2016:1225-1234.
[3]Ou M, Cui P, Pei J, Zhu W. Asymmetric Transitivity Preserving Graph Embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2016:1105-1114.
[4]Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM Press, 2014: 701-710.
[5]Chang S, Han W, Tang J. Heterogeneous Network Embedding via Deep Architecture[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2015:119-128.
[6] Tang J, Qu M, Wang M.LINE: Large-scale Information Network Embedding[C]//Proceedings of the 24th International Conference on World Wide Web.2015: 1067-1077.
[7] Grover A, Leskovec J. 2016. node2vec: Scalable Feature Learning for Networks[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2016: 855-864.
[8] Riberio L F R， Saverese P H P， Figueiredo D R.Struc2vec: Learning Node Representations from Structural Identity[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2017: 385-394.
[9] Dong Y, Chawla N V. Anathram Swami.metapath2vec: Scalable Representation Learning for Heterogeneous Networks[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2017: 135-144.
[10] Li M, Andersen D, Smola A, et al. Scaling Distributed Machine Learning with the Parameter Server[C]//In Operating Systems Design and Implementation (OSDI), 2014.
[11] Li M, Andersen D, Smola A, et al. Communication Efficient Distributed Machine Learning with the Parameter Server[C]//Proceedings of Neural Information Processing Systems (NIPS), 2014: 19-27.
[12] Ordentlich E, Yang L, Feng A, et al. Network-Efficient Distributed Word2vec Training System for Large Vocabularies[C]//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM Press, 2016: 1139-1148.
所有评论仅代表网友意见